import java.util.*;

        import static java.lang.System.exit;

public class Exchange {
    public int [] penny;
    public int n;
    public int aim;

    public Exchange(int[] penny, int n, int aim) {
        this.penny = penny;
        this.n = n;
        this.aim = aim;
    }

    public int countWays() {
        // write code here
        if (n == 0 || penny == null || aim < 0) {
            exit(0);
        }
        int[][] pd = new int[n][aim + 1];
        for (int i = 0; i < n; i++) {
            pd[i][0] = 1;
        }
        for (int i = 1; penny[0] * i <= aim; i++) {
            pd[0][penny[0] * i] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= aim; j++) {
                if (j >= penny[i]) {
                    pd[i][j] = pd[i - 1][j] + pd[i][j - penny[i]];
                } else {
                    pd[i][j] = pd[i - 1][j];
                }
            }
        }
        return pd[n-1][aim];
    }


    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        System.out.println("请输入可找回零钱个数：");
        int number=sc.nextInt();
        int [] penny=new int[number];
        System.out.println("请依次输入可找回零钱面值");
        for(int i=0;i<number;i++){
            penny[i]=sc.nextInt();
        }

        System.out.print("可找回面值有：");
        for(int i=0;i<number;i++){
            System.out.print(penny[i]+" ");
        }

        System.out.println();
        System.out.print("请输入需要找回的零钱总数:");
        int aim=sc.nextInt();

        int n=penny.length;
        Exchange exchange=new Exchange(penny,n,aim);
        System.out.println("一共有"+exchange.countWays()+"中找零钱的方式");
    }
}

//走方格问题
//import java.util.*;
//public class MinimumPath {
//    public int getMin(int[][] map, int n, int m) {
//        // write code here
//        int[][] dp = new int[n][m];
//        for(int i=0;i<n;i++){
//            for(int j=0;j<=i;j++){
//                dp[i][0]+=map[j][0];
//            }
//        }
//        for(int i=0;i<m;i++){
//            for(int j=0;j<=i;j++){
//                dp[0][i]+=map[0][j];
//            }
//        }
//        for(int i=1;i<n;i++){
//            for(int j=1;j<m;j++){
//                dp[i][j] = min(dp[i][j-1]+map[i][j],dp[i-1][j]+map[i][j]);
//            }
//        }
//        return dp[n-1][m-1];
//    }
//    public int min(int a,int b){
//        if(a>b){
//            return b;
//        }else{
//            return a;
//        }
//    }
